<!DOCTYPE html>
<html lang="zh-Hans">
<head>

    <!--[if lt IE 9]>
        <style>body {display: none; background: none !important} </style>
        <meta http-equiv="Refresh" Content="0; url=//outdatedbrowser.com/" />
    <![endif]-->

<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge, chrome=1" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">
<meta name="format-detection" content="telephone=no" />
<meta name="author" content="Bingo" />



<meta name="description" content="区间更新,以及另外一套模板">
<meta property="og:type" content="article">
<meta property="og:title" content="线段树学习笔记-6-区间更新">
<meta property="og:url" content="http://blog.acbingo.cn/2015/08/18/线段树学习笔记-6-区间更新/index.html">
<meta property="og:site_name" content="Bingo's Blog">
<meta property="og:description" content="区间更新,以及另外一套模板">
<meta property="og:image" content="http://dongxicheng.org/wp-content/uploads/2011/04/update.jpg">
<meta property="og:updated_time" content="2015-08-18T12:11:29.000Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="线段树学习笔记-6-区间更新">
<meta name="twitter:description" content="区间更新,以及另外一套模板">
<meta name="twitter:image" content="http://dongxicheng.org/wp-content/uploads/2011/04/update.jpg">

<link rel="apple-touch-icon" href= "/apple-touch-icon.png">


    <link rel="alternate" href="/atom.xml" title="Bingo&#39;s Blog" type="application/atom+xml">



    <link rel="shortcut icon" href="/favicon.png">





    <link href="//cdn.bootcss.com/fancybox/2.1.5/jquery.fancybox.min.css" rel="stylesheet">



    <script src="//cdn.bootcss.com/pace/1.0.2/pace.min.js"></script>
    <link href="//cdn.bootcss.com/pace/1.0.2/themes/blue/pace-theme-minimal.css" rel="stylesheet">


<link rel="stylesheet" href="/css/style.css">



<link href="//cdn.bootcss.com/font-awesome/4.6.3/css/font-awesome.min.css" rel="stylesheet">


<title>线段树学习笔记-6-区间更新 | Bingo&#39;s Blog</title>

<script src="//cdn.bootcss.com/jquery/2.2.4/jquery.min.js"></script>
<script src="//cdn.bootcss.com/clipboard.js/1.5.10/clipboard.min.js"></script>

<script>
    var yiliaConfig = {
        fancybox: true,
        animate: false,
        isHome: false,
        isPost: true,
        isArchive: false,
        isTag: false,
        isCategory: false,
        fancybox_js: "//cdn.bootcss.com/fancybox/2.1.5/jquery.fancybox.min.js",
        scrollreveal: "//cdn.bootcss.com/scrollReveal.js/3.1.4/scrollreveal.min.js",
        search: true
    }
</script>


    <script> yiliaConfig.jquery_ui = [false]; </script>



    <script> yiliaConfig.rootUrl = "\/";</script>






</head>
<body>
  <div id="container">
    <div class="left-col">
    <div class="overlay"></div>
<div class="intrude-less">
    <header id="header" class="inner">
        <a href="/" class="profilepic">
            <img src="/img/avatar.png" class="animated zoomIn">
        </a>
        <hgroup>
          <h1 class="header-author"><a href="/">Bingo</a></h1>
        </hgroup>

        
        <p class="header-subtitle">Here&#39;s My Second Brains</p>
        

        
            <form id="search-form">
            <input type="text" id="local-search-input" name="q" placeholder="search..." class="search form-control" autocomplete="off" autocorrect="off" searchonload="false" />
            <i class="fa fa-times" onclick="resetSearch()"></i>
            </form>
            <div id="local-search-result"></div>
            <p class='no-result'>No results found <i class='fa fa-spinner fa-pulse'></i></p>
        


        
            <div id="switch-btn" class="switch-btn">
                <div class="icon">
                    <div class="icon-ctn">
                        <div class="icon-wrap icon-house" data-idx="0">
                            <div class="birdhouse"></div>
                            <div class="birdhouse_holes"></div>
                        </div>
                        <div class="icon-wrap icon-ribbon hide" data-idx="1">
                            <div class="ribbon"></div>
                        </div>
                        
                        <div class="icon-wrap icon-link hide" data-idx="2">
                            <div class="loopback_l"></div>
                            <div class="loopback_r"></div>
                        </div>
                        
                        
                        <div class="icon-wrap icon-me hide" data-idx="3">
                            <div class="user"></div>
                            <div class="shoulder"></div>
                        </div>
                        
                    </div>
                    
                </div>
                <div class="tips-box hide">
                    <div class="tips-arrow"></div>
                    <ul class="tips-inner">
                        <li>菜单</li>
                        <li>标签</li>
                        
                        <li>友情链接</li>
                        
                        
                        <li>关于我</li>
                        
                    </ul>
                </div>
            </div>
        

        <div id="switch-area" class="switch-area">
            <div class="switch-wrap">
                <section class="switch-part switch-part1">
                    <nav class="header-menu">
                        <ul>
                        
                            <li><a href="/">主页</a></li>
                        
                            <li><a href="/archives/">所有文章</a></li>
                        
                            <li><a href="/tags/">标签云</a></li>
                        
                            <li><a href="http://acbingo.cn/">关于我</a></li>
                        
                        </ul>
                    </nav>
                    <nav class="header-nav">
                        <ul class="social">
                            
                                <a class="fa Email" href="/&#116;&#x66;&#117;&#116;&#121;&#x40;&#x71;&#113;&#46;&#99;&#111;&#109;" title="Email"></a>
                            
                                <a class="fa GitHub" href="https://github.com/ACBingo" title="GitHub"></a>
                            
                                <a class="fa 知乎" href="https://www.zhihu.com/people/li-bing-59-10" title="知乎"></a>
                            
                                <a class="fa StackOverflow" href="http://stackoverflow.com/users/6059386/acbingo" title="StackOverflow"></a>
                            
                        </ul>
                    </nav>
                </section>
                
                
                <section class="switch-part switch-part2">
                    <div class="widget tagcloud" id="js-tagcloud">
                        <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/Android/">Android</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Array/">Array</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Hash-Table/">Hash Table</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/KMP/">KMP</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/LeetCode/">LeetCode</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Linked-List/">Linked List</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Math/">Math</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/STL/">STL</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/String/">String</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/android/">android</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/anroid/">anroid</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/books/">books</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/c/">c#</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/c/">c++</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/cocos/">cocos</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/cocos2dx/">cocos2dx</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/const/">const</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/coursera/">coursera</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/git/">git</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/github/">github</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/hash/">hash</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/hdu/">hdu</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/hexo/">hexo</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/linux/">linux</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/markdown/">markdown</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/offer/">offer</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/other/">other</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/poj/">poj</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/shadowsocks/">shadowsocks</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/string/">string</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/ubuntu/">ubuntu</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/uva/">uva</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/vim/">vim</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/二分/">二分</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/二叉树/">二叉树</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/位运算/">位运算</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/其它/">其它</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/分治/">分治</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/动态规划/">动态规划</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/单调队列/">单调队列</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/回溯/">回溯</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/字符串/">字符串</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/字符串匹配/">字符串匹配</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/指针/">指针</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/排序/">排序</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/操作系统/">操作系统</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/数据结构/">数据结构</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/枚举/">枚举</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/树/">树</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/算法/">算法</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/红黑树/">红黑树</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/线段树/">线段树</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/继承/">继承</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/编译原理/">编译原理</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/虚函数/">虚函数</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/逆序对/">逆序对</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/递归/">递归</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/链表/">链表</a></li></ul>
                    </div>
                </section>
                
                
                
                <section class="switch-part switch-part3">
                    <div id="js-friends">
                    
                      <a class="main-nav-link switch-friends-link" href="https://hexo.io">Hexo</a>
                    
                      <a class="main-nav-link switch-friends-link" href="https://pages.github.com/">GitHub</a>
                    
                      <a class="main-nav-link switch-friends-link" href="http://moxfive.xyz/">MOxFIVE</a>
                    
                    </div>
                </section>
                

                
                
                <section class="switch-part switch-part4">
                
                    <div id="js-aboutme">专注于前端</div>
                </section>
                
            </div>
        </div>
    </header>                
</div>
    </div>
    <div class="mid-col">
      <nav id="mobile-nav">
      <div class="overlay">
          <div class="slider-trigger"></div>
          <h1 class="header-author js-mobile-header hide"><a href="/" title="回到主页">Bingo</a></h1>
      </div>
    <div class="intrude-less">
        <header id="header" class="inner">
            <a href="/" class="profilepic">
                <img src="/img/avatar.png" class="animated zoomIn">
            </a>
            <hgroup>
              <h1 class="header-author"><a href="/" title="回到主页">Bingo</a></h1>
            </hgroup>
            
            <p class="header-subtitle">Here&#39;s My Second Brains</p>
            
            <nav class="header-menu">
                <ul>
                
                    <li><a href="/">主页</a></li>
                
                    <li><a href="/archives/">所有文章</a></li>
                
                    <li><a href="/tags/">标签云</a></li>
                
                    <li><a href="http://acbingo.cn/">关于我</a></li>
                
                <div class="clearfix"></div>
                </ul>
            </nav>
            <nav class="header-nav">
                        <ul class="social">
                            
                                <a class="fa Email" target="_blank" href="/&#116;&#x66;&#117;&#116;&#121;&#x40;&#x71;&#113;&#46;&#99;&#111;&#109;" title="Email"></a>
                            
                                <a class="fa GitHub" target="_blank" href="https://github.com/ACBingo" title="GitHub"></a>
                            
                                <a class="fa 知乎" target="_blank" href="https://www.zhihu.com/people/li-bing-59-10" title="知乎"></a>
                            
                                <a class="fa StackOverflow" target="_blank" href="http://stackoverflow.com/users/6059386/acbingo" title="StackOverflow"></a>
                            
                        </ul>
            </nav>
        </header>                
    </div>
    <link class="menu-list" tags="标签" friends="友情链接" about="关于我"/>
</nav>
      <div class="body-wrap"><article id="post-线段树学习笔记-6-区间更新" class="article article-type-post" itemscope itemprop="blogPost">
  
    <div class="article-meta">
      <a href="/2015/08/18/线段树学习笔记-6-区间更新/" class="article-date">
      <time datetime="2015-08-18T08:14:21.000Z" itemprop="datePublished">2015-08-18</time>
</a>


    </div>
  
  <div class="article-inner">
    
      <input type="hidden" class="isFancy" />
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      线段树学习笔记-6-区间更新
    </h1>
  

      </header>
      
      <div class="article-info article-info-post">
        

        
    <div class="article-tag tagcloud">
        <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/线段树/">线段树</a></li></ul>
    </div>

        <div class="clearfix"></div>
      </div>
      
    
    <div class="article-entry" itemprop="articleBody">
      
          
        <p>本文参考自<a href="http://dongxicheng.org/structure/segment-tree/" target="_blank" rel="external">董的博客</a>,讲的很清楚啊，可见作者思路很清晰，膜拜Orz</p>
<h1 id="区间查询"><a href="#区间查询" class="headerlink" title="区间查询"></a>区间查询</h1><p>区间查询指用户输入一个区间，获取该区间的有关信息，如区间中最大值，最小值，第N大的值等。<br>比如前面一个图中所示的树，如果询问区间是[0,2]，或者询问的区间是[3,3]，不难直接找到对应的节点回答这一问题。但并不是所有的提问都这么容易回答，比如[0,3]，就没有哪一个节点记录了这个区间的最小值。当然，解决方法也不难找到：把[0,2]和[3,3]两个区间（它们在整数意义上是相连的两个区间）的最小值“合并”起来，也就是求这两个最小值的最小值，就能求出[0,3]范围的最小值。同理，对于其他询问的区间，也都可以找到若干个相连的区间，合并后可以得到询问的区间。<br>区间查询的伪代码如下：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div></pre></td><td class="code"><pre><div class="line">// node 为线段树的结点类型，其中Left 和Right 分别表示区间左右端点</div><div class="line"> </div><div class="line">// Lch 和Rch 分别表示指向左右孩子的指针</div><div class="line"> </div><div class="line">void Query(node *p, int a, int b) // 当前考察结点为p，查询区间为(a,b]</div><div class="line"> </div><div class="line">&#123;</div><div class="line"> </div><div class="line">  if (a &lt;= p-&gt;Left &amp;&amp; p-&gt;Right &lt;= b)</div><div class="line"> </div><div class="line">  // 如果当前结点的区间包含在查询区间内</div><div class="line"> </div><div class="line">  &#123;</div><div class="line"> </div><div class="line">     ...... // 更新结果</div><div class="line"> </div><div class="line">     return;</div><div class="line"> </div><div class="line">  &#125;</div><div class="line"> </div><div class="line">  Push_Down(p); // 等到下面的修改操作再解释这句</div><div class="line"> </div><div class="line">  int mid = (p-&gt;Left + p-&gt;Right) / 2; // 计算左右子结点的分隔点</div><div class="line"> </div><div class="line">  if (a &lt; mid) Query(p-&gt;Lch, a, b); // 和左孩子有交集，考察左子结点</div><div class="line"> </div><div class="line">  if (b &gt; mid) Query(p-&gt;Rch, a, b); // 和右孩子有交集，考察右子结点</div><div class="line"> </div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<p>可见，这样的过程一定选出了尽量少的区间，它们相连后正好涵盖了整个[l,r]，没有重复也没有遗漏。同时，考虑到线段树上每层的节点最多会被选取2个，一共选取的节点数也是O(log n)的，因此查询的时间复杂度也是O(log n)。<br>线段树并不适合所有区间查询情况，它的使用条件是“相邻的区间的信息可以被合并成两个区间的并区间的信息”。即问题是可以被分解解决的。</p>
<h1 id="区间修改"><a href="#区间修改" class="headerlink" title="区间修改"></a>区间修改</h1><p>当用户修改一个区间的值时，如果连同其子孙全部修改，则改动的节点数必定会远远超过O(log n)个。因而，如果要想把区间修改操作也控制在O(log n)的时间内，只修改O(log n)个节点的信息就成为必要。<br>借鉴前一节区间查询用到的思路：区间修改时如果修改了一个节点所表示的区间，也不用去修改它的儿子节点。然而，对于被修改节点的祖先节点，也必须更新它所记录的值，否则查询操作就肯定会出问题（正如修改单个节点的情况一样）。<br>这些选出的节点的祖先节点直接更新值即可，而选出的节点的子孙却显然不能这么简单地处理：每个节点的值必须能由两个儿子节点的值得到，如这幅图中的例子：<br><img src="http://dongxicheng.org/wp-content/uploads/2011/04/update.jpg" alt=""><br>这里，节点[0,1]的值应该是4，但是两个儿子的值又分别是3和5。如果查询[0,0]区间的RMQ，算出来的结果会是3，而正确答案显然是4。<br>问题显然在于，尽管修改了一个节点以后，不用修改它的儿子节点，但是它的儿子节点的信息事实上已经被改变了。这就需要我们在节点里增设一个域：标记。把对节点的修改情况储存在标记里面，这样，当我们自上而下地访问某节点时，就能把一路上所遇到的所有标记都考虑进去。<br>但是，在一个节点带上标记时，会给更新这个节点的值带来一些麻烦。继续上面的例子，如果我把位置0的数字从4改成了3，区间[0,0]的值应该变回3，但实际上，由于区间[0,1]有一个“添加了1”的标记，如果直接把值修改为3，则查询区间[0,0]的时候我们会得到3+1=4这个错误结果。但是，把这个3改成2，虽然正确，却并不直观，更不利于推广（参见下面的一个例子）。<br>为此我们引入延迟标记的一些概念。每个结点新增加一个标记，记录这个结点是否被进行了某种修改操作(这种修改操作会影响其子结点)。还是像上面的一样，对于任意区间的修改，我们先按照查询的方式将其划分成线段树中的结点，然后修改这些结点的信息，并给这些结点标上代表这种修改操作的标记。在修改和查询的时候，如果我们到了一个结点p ，并且决定考虑其子结点，那么我们就要看看结点p 有没有标记，如果有，就要按照标记修改其子结点的信息，并且给子结点都标上相同的标记，同时消掉p 的标记。代码框架为：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div></pre></td><td class="code"><pre><div class="line">// node 为线段树的结点类型，其中Left 和Right 分别表示区间左右端点</div><div class="line"> </div><div class="line">// Lch 和Rch 分别表示指向左右孩子的指针</div><div class="line"> </div><div class="line">void Change(node *p, int a, int b) // 当前考察结点为p，修改区间为(a,b]</div><div class="line"> </div><div class="line">&#123;</div><div class="line"> </div><div class="line">  if (a &lt;= p-&gt;Left &amp;&amp; p-&gt;Right &lt;= b)</div><div class="line"> </div><div class="line">  // 如果当前结点的区间包含在修改区间内</div><div class="line"> </div><div class="line">  &#123;</div><div class="line"> </div><div class="line">     ...... // 修改当前结点的信息，并标上标记</div><div class="line"> </div><div class="line">     return;</div><div class="line"> </div><div class="line">  &#125;</div><div class="line"> </div><div class="line">  Push_Down(p); // 把当前结点的标记向下传递</div><div class="line"> </div><div class="line">  int mid = (p-&gt;Left + p-&gt;Right) / 2; // 计算左右子结点的分隔点</div><div class="line"> </div><div class="line">  if (a &lt; mid) Change(p-&gt;Lch, a, b); // 和左孩子有交集，考察左子结点</div><div class="line"> </div><div class="line">  if (b &gt; mid) Change(p-&gt;Rch, a, b); // 和右孩子有交集，考察右子结点</div><div class="line"> </div><div class="line">  Update(p); // 维护当前结点的信息（因为其子结点的信息可能有更改）</div><div class="line"> </div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<h1 id="模板"><a href="#模板" class="headerlink" title="模板"></a>模板</h1><p>本模板搬自<a href="http://blog.csdn.net/metalseed/article/details/8039326" target="_blank" rel="external">这里</a></p>
<h2 id="模板1"><a href="#模板1" class="headerlink" title="模板1"></a>模板1</h2><p>RMQ，查询区间最值下标—min<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div></pre></td><td class="code"><pre><div class="line">#include&lt;iostream&gt;    </div><div class="line">  </div><div class="line">using namespace std;    </div><div class="line">    </div><div class="line">#define MAXN 100    </div><div class="line">#define MAXIND 256 //线段树节点个数    </div><div class="line">    </div><div class="line">//构建线段树,目的:得到M数组.    </div><div class="line">void build(int node, int b, int e, int M[], int A[])    </div><div class="line">&#123;    </div><div class="line">    if (b == e)    </div><div class="line">        M[node] = b; //只有一个元素,只有一个下标    </div><div class="line">    else    </div><div class="line">    &#123;     </div><div class="line">        build(2 * node, b, (b + e) / 2, M, A);    </div><div class="line">        build(2 * node + 1, (b + e) / 2 + 1, e, M, A);    </div><div class="line">  </div><div class="line">        if (A[M[2 * node]] &lt;= A[M[2 * node + 1]])    </div><div class="line">            M[node] = M[2 * node];    </div><div class="line">        else    </div><div class="line">            M[node] = M[2 * node + 1];    </div><div class="line">    &#125;    </div><div class="line">&#125;    </div><div class="line">    </div><div class="line">//找出区间 [i, j] 上的最小值的索引    </div><div class="line">int query(int node, int b, int e, int M[], int A[], int i, int j)    </div><div class="line">&#123;    </div><div class="line">    int p1, p2;    </div><div class="line">    </div><div class="line">    //查询区间和要求的区间没有交集    </div><div class="line">    if (i &gt; e || j &lt; b)    </div><div class="line">        return -1;    </div><div class="line">  </div><div class="line">    if (b &gt;= i &amp;&amp; e &lt;= j)    </div><div class="line">        return M[node];    </div><div class="line">   </div><div class="line">    p1 = query(2 * node, b, (b + e) / 2, M, A, i, j);    </div><div class="line">    p2 = query(2 * node + 1, (b + e) / 2 + 1, e, M, A, i, j);    </div><div class="line">    </div><div class="line">    //return the position where the overall    </div><div class="line">    //minimum is    </div><div class="line">    if (p1 == -1)    </div><div class="line">        return M[node] = p2;    </div><div class="line">    if (p2 == -1)    </div><div class="line">        return M[node] = p1;    </div><div class="line">    if (A[p1] &lt;= A[p2])    </div><div class="line">        return M[node] = p1;    </div><div class="line">    return M[node] = p2;    </div><div class="line">    </div><div class="line">&#125;    </div><div class="line">    </div><div class="line">    </div><div class="line">int main()    </div><div class="line">&#123;    </div><div class="line">    int M[MAXIND]; //下标1起才有意义,否则不是二叉树,保存下标编号节点对应区间最小值的下标.    </div><div class="line">    memset(M,-1,sizeof(M));    </div><div class="line">    int a[]=&#123;3,4,5,7,2,1,0,3,4,5&#125;;    </div><div class="line">    build(1, 0, sizeof(a)/sizeof(a[0])-1, M, a);    </div><div class="line">    cout&lt;&lt;query(1, 0, sizeof(a)/sizeof(a[0])-1, M, a, 0, 5)&lt;&lt;endl;    </div><div class="line">    return 0;    </div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<h2 id="模板2"><a href="#模板2" class="headerlink" title="模板2"></a>模板2</h2><p>连续区间修改或者单节点更新的动态查询问题 （此模板查询区间和）<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div></pre></td><td class="code"><pre><div class="line">#include &lt;cstdio&gt;    </div><div class="line">#include &lt;algorithm&gt;    </div><div class="line">using namespace std;    </div><div class="line">     </div><div class="line">#define lson l , m , rt &lt;&lt; 1    </div><div class="line">#define rson m + 1 , r , rt &lt;&lt; 1 | 1   </div><div class="line">#define root 1 , N , 1   </div><div class="line">#define LL long long    </div><div class="line">const int maxn = 111111;    </div><div class="line">LL add[maxn&lt;&lt;2];    </div><div class="line">LL sum[maxn&lt;&lt;2];    </div><div class="line">void PushUp(int rt) &#123;    </div><div class="line">    sum[rt] = sum[rt&lt;&lt;1] + sum[rt&lt;&lt;1|1];    </div><div class="line">&#125;    </div><div class="line">void PushDown(int rt,int m) &#123;    </div><div class="line">    if (add[rt]) &#123;    </div><div class="line">        add[rt&lt;&lt;1] += add[rt];    </div><div class="line">        add[rt&lt;&lt;1|1] += add[rt];    </div><div class="line">        sum[rt&lt;&lt;1] += add[rt] * (m - (m &gt;&gt; 1));    </div><div class="line">        sum[rt&lt;&lt;1|1] += add[rt] * (m &gt;&gt; 1);    </div><div class="line">        add[rt] = 0;    </div><div class="line">    &#125;    </div><div class="line">&#125;    </div><div class="line">void build(int l,int r,int rt) &#123;    </div><div class="line">    add[rt] = 0;    </div><div class="line">    if (l == r) &#123;    </div><div class="line">        scanf(&quot;%lld&quot;,&amp;sum[rt]);    </div><div class="line">        return ;    </div><div class="line">    &#125;    </div><div class="line">    int m = (l + r) &gt;&gt; 1;    </div><div class="line">    build(lson);    </div><div class="line">    build(rson);    </div><div class="line">    PushUp(rt);    </div><div class="line">&#125;    </div><div class="line">void update(int L,int R,int c,int l,int r,int rt) &#123;    </div><div class="line">    if (L &lt;= l &amp;&amp; r &lt;= R) &#123;    </div><div class="line">        add[rt] += c;    </div><div class="line">        sum[rt] += (LL)c * (r - l + 1);    </div><div class="line">        return ;    </div><div class="line">    &#125;    </div><div class="line">    PushDown(rt , r - l + 1);    </div><div class="line">    int m = (l + r) &gt;&gt; 1;    </div><div class="line">    if (L &lt;= m) update(L , R , c , lson);    </div><div class="line">    if (m &lt; R) update(L , R , c , rson);    </div><div class="line">    PushUp(rt);    </div><div class="line">&#125;    </div><div class="line">LL query(int L,int R,int l,int r,int rt) &#123;    </div><div class="line">    if (L &lt;= l &amp;&amp; r &lt;= R) &#123;    </div><div class="line">        return sum[rt];    </div><div class="line">    &#125;    </div><div class="line">    PushDown(rt , r - l + 1);    </div><div class="line">    int m = (l + r) &gt;&gt; 1;    </div><div class="line">    LL ret = 0;    </div><div class="line">    if (L &lt;= m) ret += query(L , R , lson);    </div><div class="line">    if (m &lt; R) ret += query(L , R , rson);    </div><div class="line">    return ret;    </div><div class="line">&#125;    </div><div class="line">int main() &#123;    </div><div class="line">    int N , Q;    </div><div class="line">    scanf(&quot;%d%d&quot;,&amp;N,&amp;Q);    </div><div class="line">    build(root);    </div><div class="line">    while (Q --) &#123;    </div><div class="line">        char op[2];    </div><div class="line">        int a , b , c;    </div><div class="line">        scanf(&quot;%s&quot;,op);    </div><div class="line">        if (op[0] == &apos;Q&apos;) &#123;    </div><div class="line">            scanf(&quot;%d%d&quot;,&amp;a,&amp;b);    </div><div class="line">            printf(&quot;%lld\n&quot;,query(a , b ,root));    </div><div class="line">        &#125; else &#123;    </div><div class="line">            scanf(&quot;%d%d%d&quot;,&amp;a,&amp;b,&amp;c);    </div><div class="line">            update(a , b , c , root);    </div><div class="line">        &#125;    </div><div class="line">    &#125;    </div><div class="line">    return 0;    </div><div class="line">&#125;</div></pre></td></tr></table></figure></p>

      
    </div>
    
  </div>
  
    
    <div class="copyright">
        <p><span>本文标题:</span><a href="/2015/08/18/线段树学习笔记-6-区间更新/">线段树学习笔记-6-区间更新</a></p>
        <p><span>文章作者:</span><a href="/" title="回到主页">Bingo</a></p>
        <p><span>发布时间:</span>2015-08-18, 16:14:21</p>
        <p><span>最后更新:</span>2015-08-18, 20:11:29</p>
        <p>
            <span>原始链接:</span><a class="post-url" href="/2015/08/18/线段树学习笔记-6-区间更新/" title="线段树学习笔记-6-区间更新">http://blog.acbingo.cn/2015/08/18/线段树学习笔记-6-区间更新/</a>
            <span class="copy-path" data-clipboard-text="原文: http://blog.acbingo.cn/2015/08/18/线段树学习笔记-6-区间更新/　　作者: Bingo" title="点击复制文章链接"><i class="fa fa-clipboard"></i></span>
            <script> var clipboard = new Clipboard('.copy-path'); </script>
        </p>
        <p>
            <span>许可协议:</span><i class="fa fa-creative-commons"></i> <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/" title="CC BY-NC-SA 4.0 International" target = "_blank">"署名-非商用-相同方式共享 4.0"</a> 转载请保留原文链接及作者。
        </p>
    </div>



    <nav id="article-nav">
        
            <div id="article-nav-newer" class="article-nav-title">
                <a href="/2015/08/18/线段树学习笔记-7-hdu1698/">
                    线段树学习笔记-7-hdu1698
                </a>
            </div>
        
        
            <div id="article-nav-older" class="article-nav-title">
                <a href="/2015/08/18/Coursera_程序设计与算法_C程序设计进阶/">
                    Coursera_程序设计与算法_C程序设计进阶
                </a>
            </div>
        
    </nav>

  
</article>

    <div id="toc" class="toc-article">
        <strong class="toc-title">文章目录</strong>
        
            <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#区间查询"><span class="toc-number">1.</span> <span class="toc-text">区间查询</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#区间修改"><span class="toc-number">2.</span> <span class="toc-text">区间修改</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#模板"><span class="toc-number">3.</span> <span class="toc-text">模板</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#模板1"><span class="toc-number">3.1.</span> <span class="toc-text">模板1</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#模板2"><span class="toc-number">3.2.</span> <span class="toc-text">模板2</span></a></li></ol></li></ol>
        
    </div>
    <style>
        .left-col .switch-btn,
        .left-col .switch-area {
            display: none;
        }
        .toc-level-3 i,
        .toc-level-3 ol {
            display: none !important;
        }
    </style>

    <input type="button" id="tocButton" value="隐藏目录"  title="点击按钮隐藏或者显示文章目录">

    <script>
        yiliaConfig.toc = ["隐藏目录", "显示目录", !!"false"];
    </script>



    
<div class="share">
    
        <div class="bdsharebuttonbox">
            <a href="#" class="fa fa-twitter bds_twi" data-cmd="twi" title="分享到推特"></a>
            <a href="#" class="fa fa-weibo bds_tsina" data-cmd="tsina" title="分享到新浪微博"></a>
            <a href="#" class="fa fa-qq bds_sqq" data-cmd="sqq" title="分享给 QQ 好友"></a>
            <a href="#" class="fa fa-files-o bds_copy" data-cmd="copy" title="复制网址"></a>
            <a href="#" class="fa fa fa-envelope-o bds_mail" data-cmd="mail" title="通过邮件分享"></a>
            <a href="#" class="fa fa-weixin bds_weixin" data-cmd="weixin" title="生成文章二维码"></a>
            <a href="#" class="fa fa-share-alt bds_more" data-cmd="more"></i></a>
        </div>
        <script>
            window._bd_share_config={
                "common":{"bdSnsKey":{},"bdText":"线段树学习笔记-6-区间更新　| Bingo's Blog　","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];
        </script>
    

    
</div>







    
      <div class="duoshuo" id="comments">
    <div id="comment-box" ></div>
    <div class="ds-thread" id="ds-thread" data-thread-key="2015/08/18/线段树学习笔记-6-区间更新/" data-title="线段树学习笔记-6-区间更新" data-url="http://blog.acbingo.cn/2015/08/18/线段树学习笔记-6-区间更新/"></div>
    <script>
        var duoshuoQuery = {short_name:"acbingo"};
        var loadComment = function(){
            var d = document, s = d.createElement('script');
            s.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + '//static.duoshuo.com/embed.js';
            s.async = true; s.charset = 'UTF-8';
            (d.head || d.body).appendChild(s);
        }

        
    </script>
    
    <script> loadComment(); </script>

</div>
    




    <div class="scroll" id="post-nav-button">
        
            <a href="/2015/08/18/线段树学习笔记-7-hdu1698/" title="上一篇: 线段树学习笔记-7-hdu1698">
                <i class="fa fa-angle-left"></i>
            </a>
        

        <a title="文章列表"><i class="fa fa-bars"></i><i class="fa fa-times"></i></a>

        
            <a href="/2015/08/18/Coursera_程序设计与算法_C程序设计进阶/" title="下一篇: Coursera_程序设计与算法_C程序设计进阶">
                <i class="fa fa-angle-right"></i>
            </a>
        
    </div>

    <ul class="post-list"><li class="post-list-item"><a class="post-list-link" href="/2016/08/07/c++初始化列表/">c++初始化列表</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/08/05/一步一步学习红黑树-2/">一步一步学习红黑树-2</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/08/04/一步一步学习红黑树/">一步一步学习红黑树-1</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/08/03/回文解码/">回文解码</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/08/03/C++中虚析构函数的作用/">C++中虚析构函数的作用</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/08/03/const/">const</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/08/03/const与常成员函数/">const与常成员函数</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/31/虚拟继承/">虚拟继承</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/31/函数指针/">函数指针</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/28/记事本/">记事本</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/28/StarFiles/">StarFiles</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/28/酒店管理系统/">酒店管理系统</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/28/飞机大战/">飞机大战</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/27/仿函数/">仿函数/函数对象</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/27/二叉树中和为某一值的路径/">二叉树中和为某一值的路径</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/26/递归实现反转列表/">递归实现反转链表</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/26/快速幂/">快速幂</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/26/bitset的用法/">bitset的用法</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/26/二分查找、归并排序和快速排序/">二分查找、归并排序和快速排序</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/25/重建二叉树/">重建二叉树</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/25/leetcode_5/">LeetCode_5:Longest Palindromic Substring</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/24/leetcode_4/">LeetCode_4:Median of Two Sorted Arrays</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/24/leetcode_3/">LeetCode_3:Longest Substring Without Repeating Characters</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/24/leetcode_2/">LeetCode_2:Add Two Numbers</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/07/24/leetcode_1_Two Sum/">LeetCode_1:Two Sum</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/06/07/Bingo's_ShadowSocks使用说明/">Bingo's_Shadowsocks</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/05/03/如何优雅的开启wifi热点/">如何优雅的开启wifi热点</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/05/02/如何优雅的连接指定wifi热点/">如何优雅的连接指定wifi热点</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/05/02/对AndroidWifi状态广播的研究/">对AndroidWifi状态广播的研究</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/05/01/coursera数据结构_字符串_课后作业/">coursera数据结构_字符串_课后作业</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/05/01/简单几步在Android_Studio上实现二维码的扫描/">简单几步在Android_Studio上实现二维码的生成与扫描</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/04/25/coursera_算法课后习题/">coursera_算法课后习题</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/04/25/coursera_计算机组成学习笔记/">coursera_计算机组成学习笔记</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/04/20/cocos2dx-飞机大战/">cocos2dx-飞机大战</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/04/14/android_ping不通电脑/">android_ping不通电脑</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/04/14/android创建与连接热点/">android创建与连接热点</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/04/01/coursera_算法_递归/">coursera_算法_递归</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/03/30/coursera_操作系统学习笔记/">coursera_操作系统学习笔记_计算机操作系统概述</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/03/29/编译原理_中科大公开课_第一单元编译器介绍作业/">编译原理_中科大公开课_第一单元编译器介绍作业</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/03/25/关于Inflater与findViewById()的思考/">关于Inflater与findViewById()的思考</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/03/11/coursera_魔兽世界终结版/">coursera_魔兽世界终结版</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/03/05/coursera_算法作业_枚举/">coursera_算法作业_枚举</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/27/coursera_c++高级主体和c++11新特性/">coursera_c++高级主体和c++11新特性</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/27/coursera_c++期末考试/">coursera_c++期末考试</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/24/coursera_STL2作业/">coursera_STL2作业</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/21/coursera容器适配器/">coursera容器适配器_算法</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/21/coursera标准模版库STL2/">coursera标准模版库STL2</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/20/coursera编程作业-STL1/">coursera编程作业-STL1</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/20/coursera疑问/">coursera疑问</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/19/coursera学习笔记-函数对象/">coursera学习笔记-函数对象</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/01/19/coursera学习笔记-顺序容器Vector/">coursera学习笔记-顺序容器Vector、List和Deque</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/12/05/算法学习笔记-14-最长公共子序列/">算法学习笔记-14-最长公共子序列</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/12/03/算法学习笔记-13-矩阵连乘问题/">算法学习笔记-13-矩阵连乘问题</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/12/01/算法学习笔记-12-循环赛日程表/">算法学习笔记-12-循环赛日程表</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/12/01/算法学习笔记-11-最接近点对问题/">算法学习笔记-11-最接近点对问题</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/12/01/算法学习笔记-10-线性时间选择/">算法学习笔记-10-线性时间选择</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/27/算法学习笔记-9-快速排序/">算法学习笔记-9-快速排序</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/26/算法学习笔记-8-合并排序/">算法学习笔记-8-归并排序</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/24/算法学习笔记-7-棋盘覆盖问题/">算法学习笔记-7-棋盘覆盖问题</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/22/算法学习笔记-6-Strassen矩阵乘法/">算法学习笔记-6-Strassen矩阵乘法</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/21/算法学习笔记-5-Hanoi塔问题/">算法学习笔记-5-Hanoi塔问题</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/20/算法学习笔记-4-整数划分问题/">算法学习笔记-4-整数划分问题</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/19/算法学习笔记-3-排列问题/">算法学习笔记-3-排列问题</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/18/算法学习笔记-2-递归的概念/">算法学习笔记-2-递归的概念</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/17/coursera_标准模板库STL/">coursera_标准模板库STL</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/17/算法学习笔记-0-序/">算法学习笔记-0-序</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/17/算法学习笔记-1-NP完全性理论/">算法学习笔记-1-NP完全性理论</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/14/文件操作和模板_编程作业/">文件操作和模板_编程作业</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/11/ubuntu下安装最新的nodejs(v4.2.2)/">ubuntu下安装最新的nodejs(v4.2.2)</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/11/ubuntu14.04的环境变量/">ubuntu14.04的环境变量</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/11/01/coursera学习笔记_文件操作和模板/">coursera学习笔记_文件操作和模板</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/10/31/coursera学习笔记_多态和虚函数/">coursera学习笔记_多态和虚函数</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/10/28/Coursera_程序设计与晋级_继承与派生_编程作业/">Coursera_程序设计与晋级_继承与派生_编程作业</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/10/22/科大OJ-数据结构-DNA序列/">科大OJ-数据结构-DNA序列</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/10/20/科大OJ-数据结构-求表达式串的后缀表达式和值/">科大OJ-数据结构-求表达式串的后缀表达式和值</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/10/01/科大OJ-数据结构-击鼓传花/">科大OJ-数据结构-击鼓传花</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/09/30/科大OJ-数据结构-求集合的交并补集/">科大OJ-数据结构-求集合的交并补集</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/09/27/hexo无法本地访问/">hexo无法本地访问</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/09/26/继承与派生/">coursera学习笔记_继承与派生</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/09/26/大数类模板/">大数类模板</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/09/15/vimium学习笔记/">vimium学习笔记</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/09/04/程序员矩阵/">程序员矩阵</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/09/03/coursera学习笔记_运算符重载/">coursera学习笔记_运算符重载</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/09/01/写hexo博客、markdown文章时图床的挑选/">写hexo博客、markdown文章时图床的挑选</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/31/coursera学习笔记-c++程序设计/">coursera学习笔记-c++程序设计</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/29/Linux下C语言应用编程学习笔记/">Linux下C语言应用编程学习笔记</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/28/linux学习笔记2/">linux学习笔记2</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/27/Bingo's exVim/">Bingo的VIM</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/27/linux下去掉^M的方法/">linux下去掉^M的方法</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/27/vim的持久撤销功能/">vim的持久撤销功能</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/25/linux学习笔记/">linux学习笔记</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/18/线段树学习笔记-7-hdu1698/">线段树学习笔记-7-hdu1698</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/18/线段树学习笔记-6-区间更新/">线段树学习笔记-6-区间更新</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/18/Coursera_程序设计与算法_C程序设计进阶/">Coursera_程序设计与算法_C程序设计进阶</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/18/线段树学习笔记-5-hdu2795/">线段树学习笔记-5-hdu2795</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/14/线段树学习笔记-4-hdu1394/">线段树学习笔记-4-hdu1394</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/14/求逆序对的个数/">求逆序对的个数</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/14/线段树学习笔记-3-hdu1754/">线段树学习笔记-3-hdu1754</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/13/线段树学习笔记-2-hdu1166/">线段树学习笔记-2-hdu1166</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/13/线段树学习笔记/">线段树学习笔记-1-入门</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/11/Coursera_程序设计与算法_计算导论与C语言基础_期末编程测试/">Coursera_程序设计与算法_计算导论与C语言基础_期末编程测试</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/10/Coursera_程序设计与算法_C程序设计进阶_C程序中的函数/">Coursera_程序设计与算法_计算导论与C语言基础_数组应用练习</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/10/Coursera_程序设计与算法_计算导论与C语言基础_数组应用练习/">Coursera_程序设计与算法_计算导论与C语言基础_数组应用练习</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/10/hdu4821 String/">hdu4821 String</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/09/Rolling Hash(Rabin-Karp算法)匹配字符串/">Rolling Hash(Rabin-Karp算法)匹配字符串</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/09/设置vim的默认工作路径/">设置vim的默认工作路径</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/08/滑动窗口的单调队列/">滑动窗口的单调队列</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/08/08/ssh -T git@github.com出现Permission denied (publickey)/">ssh -T git@github.com出现Permission denied (publickey)</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/05/29/UVa10791-Minimum-Sum-LCM/">UVa10791-Minimum Sum LCM</a></li><li class="post-list-item"><a class="post-list-link" href="/2015/05/29/uva100/">uva100</a></li></ul>




    <script>
        
    </script>
</div>
      <footer id="footer">
    <div class="outer">
        <div id="footer-info">
            <div class="footer-left">
                <i class="fa fa-copyright"></i> 
                2014-2016 Bingo
            </div>
            <div class="footer-right">
                <a href="http://hexo.io/" target="_blank" title="快速、简洁且高效的博客框架">Hexo</a>  Theme <a href="https://github.com/MOxFIVE/hexo-theme-yelee" target="_blank" title="简而不减 Hexo 双栏博客主题  v3.5">Yelee</a> by MOxFIVE <i class="fa fa-heart animated infinite pulse"></i>
            </div>
        </div>
        
            <div class="visit">
                
                    <span id="busuanzi_container_site_pv" style='display:none'>
                        <span id="site-visit" title="本站到访数"><i class="fa fa-user" aria-hidden="true"></i><span id="busuanzi_value_site_uv"></span>
                        </span>
                    </span>
                
                
                    <span>| </span>
                
                
                    <span id="busuanzi_container_page_pv" style='display:none'>
                        <span id="page-visit"  title="本页阅读量"><i class="fa fa-eye animated infinite pulse" aria-hidden="true"></i><span id="busuanzi_value_page_pv"></span>
                        </span>
                    </span>
                
            </div>
        
    </div>
</footer>
    </div>
    
<script data-main="/js/main.js" src="//cdn.bootcss.com/require.js/2.2.0/require.min.js"></script>





<div class="scroll" id="scroll">
    <a href="#" title="返回顶部"><i class="fa fa-arrow-up"></i></a>
    <a href="#comments" onclick="load$hide();" title="查看评论"><i class="fa fa-comments-o"></i></a>
    <a href="#footer" title="转到底部"><i class="fa fa-arrow-down"></i></a>
</div>
<script>
    // Open in New Window
    
        var oOpenInNew = {
            
            
            
            
            
            
             archives: ".archive-article-title", 
             miniArchives: "a.post-list-link", 
            
             friends: "#js-friends a", 
             socail: ".social a" 
        }
        for (var x in oOpenInNew) {
            $(oOpenInNew[x]).attr("target", "_blank");
        }
    
</script>

<script async src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js">
</script>
  </div>
</body>
</html>